package NO6_Tree;

/**
 * 2025-08-18
 * 力扣 - 108. 将有序数组转换为二叉搜索树
 * <p>
 * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
 */
public class SortedArrayToBSTMain {
    public static void main(String[] args) {
        TreeNode.printTree(sortedArrayToBST(new int[]{-10, -3, 0, 5, 9}));
        TreeNode.printTreeSimple(sortedArrayToBST(new int[]{1, 3}));
    }

    public static TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0){
            return null;
        }
        if (nums.length == 1){
            return new TreeNode(nums[0]);
        }
        if (nums.length == 2){
            return new TreeNode(nums[0], null, new TreeNode(nums[1]));
        }
        return buildBST(nums, 0, nums.length - 1);
    }

    private static TreeNode buildBST(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        // 选择中间位置左边的数字作为根节点
        int mid = left + (right - left) / 2;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = buildBST(nums, left, mid - 1);
        root.right = buildBST(nums, mid + 1, right);

        return root;
    }
}
